#include <vector>
#include <unordered_set>

using std::vector;
using std::unordered_set;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> tmp;
        vector<int> flag(nums.size(), 0);
        dfs(ret, tmp, flag,nums);
        return ret;
    }

    void dfs(vector<vector<int>>& v, vector<int>& tmp, vector<int>& flag, vector<int>& nums) {
        if (tmp.size() == nums.size()) {
            v.push_back(tmp);
        }
        else {
            for (int i = 0; i < nums.size(); i++) {
                if (flag[i] == 0) {
                    flag[i] = 1;
                    tmp.push_back(nums[i]);
                    dfs(v, tmp, flag, nums);
                    tmp.pop_back();
                    flag[i] = 0;
                }
            }
        }
    }
};